package com.dong.arithmetic.tree;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * 创建树
 *
 * -         1
 * -    2          3
 * - 4    5     6     7
 * -8 9 10 11 12 13 14 15
 *
 * 根结点D、左子树L、右子树R
 * D=Degree
 * L=Left
 * R=Right
 * 结点拥有的子树数称为结点的度（Degree）
 * 根 (Root)
 * 子树 (Sub Tree)
 *
 * @author jianyang206881
 * @date 2018/7/20
 */
public class CreateTree {
    /**
     * 当前值
     */
    private int currentValue = 1;

    /**
     * 最大值
     */
    private int maxValue;

    private Map<Integer, Queue<Integer>> layerQueueMap = new HashMap<>(8);

    /**
     * 创建树
     *
     * @param num 节点数量
     * @return 树
     */
    protected TreeNote create(int num) {
        if (num <= 0) {
            return null;
        }

        // 初始化基础数据：最大值，当前层数
        this.maxValue = num;
        int layer = 1;

        // 创建父节点
        TreeNote treeNote = new TreeNote();
        treeNote.setValue(currentValue++);

        if (num == 1) {
            // 只创建父节点
            return treeNote;
        }

        // 创建子节点
        this.createChildNote(treeNote, layer);

        return treeNote;
    }

    /**
     * 创建子节点
     *
     * @param treeNote 父节点
     * @param layer    父节点所在层数
     */
    private void createChildNote(TreeNote treeNote, int layer) {

        // 往队列中放入当前层节点值
        Queue<Integer> currentLayerQueue = layerQueueMap.getOrDefault(layer, null);
        if (currentLayerQueue == null) {
            if (currentValue > maxValue) {
                return;
            }

            int queueLength = 2 << layer - 1;
            queueLength = queueLength > maxValue ? maxValue : queueLength;
            currentLayerQueue = new ArrayDeque<>(queueLength);
            for (int i = 0; i < queueLength; i++) {
                currentLayerQueue.add(currentValue++);
                if (currentValue > maxValue) {
                    break;
                }
            }
            layerQueueMap.put(layer, currentLayerQueue);
        }

        // 创建左节点
        Integer value = currentLayerQueue.poll();
        if (value != null) {
            TreeNote leftNote = new TreeNote();
            leftNote.setValue(value);
            leftNote.setParent(treeNote);
            treeNote.setLeft(leftNote);
            this.createChildNote(leftNote, layer + 1);
        }

        // 创建右节点
        value = currentLayerQueue.poll();
        if (value != null) {
            TreeNote rightNote = new TreeNote();
            rightNote.setValue(value);
            rightNote.setParent(treeNote);
            treeNote.setRight(rightNote);
            this.createChildNote(rightNote, layer + 1);
        }

    }

    class TreeNote {

        /**
         * 当前节点的值
         */
        private Integer value;
        /**
         * 父节点
         */
        private TreeNote parent;

        /**
         * 左节点
         */
        private TreeNote left;

        /**
         * 右节点
         */
        private TreeNote right;

        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }

        public TreeNote getParent() {
            return parent;
        }

        public void setParent(TreeNote parent) {
            this.parent = parent;
        }

        public TreeNote getLeft() {
            return left;
        }

        public void setLeft(TreeNote left) {
            this.left = left;
        }

        public TreeNote getRight() {
            return right;
        }

        public void setRight(TreeNote right) {
            this.right = right;
        }

    }

    public static void main(String[] args) {

        TreeNote treeNote = new CreateTree().create(1);
        TreeNote treeNote2 = new CreateTree().create(2);
        TreeNote treeNote5 = new CreateTree().create(5);
        TreeNote treeNote10 = new CreateTree().create(10);

    }
}
